【题解】 [JSOI2008]球形空间产生器高斯消元洛谷P4035

“你要求出这个n维球体的球心坐标“，这使我想到的解方程……

先假设n=2，这是一个二维平面。设圆心的坐标为$(x,y)$，有两个坐标$(a_1,b_1)$和$(a_2,b_2)$，显然两个坐标的关系为：

$(x-a_1)^2+(y-b_1)^2=(x-a_2)^2+(y-b_2)^2$

考虑如何化简上面的式子。

$(x-a_1)^2-(x-a_2)^2+(y-b_1)^2-(y-b_2)^2=0$

根据完全平方公式：

$(x-a_1)^2=x^2+a_1^2-2 \times x \times a_1$ $(x-a_1)^2-(x-a_2)^2=x^2+a_1^2-2 \times x \times a_1-x^2-a_2^2+2 \times x \times a_2$ $(x-a_1)^2-(x-a_2)^2=a_1^2-2 \times x \times a_1-a_2^2+2 \times x \times a_2$ $(x-a_1)^2-(x-a_2)^2=a_1^2-a_2^2-2(a_1-a_2)x$

同理

$(y-b_1)^2-(y-b_2)^2=b_1^2-b_2^2-2(b_1-b_2)y$

整理后：

$a_1^2-a_2^2-2(a_1-a_2)x+b_1^2-b_2^2-2(b_1-b_2)y=0$

移项后：

$a_1^2-a_2^2+b_1^2-b_2^2=2(a_1-a_2)x+2(b_1-b_2)y$

这个式子最终为：

$2(a_1-a_2)x+2(b_1-b_2)y=a_1^2-a_2^2+b_1^2-b_2^2$

由于 $a_1^2-a_2^2+b_1^2-b_2^2$ 是已知的，我们将 $a_1^2-a_2^2+b_1^2-b_2^2$ 设为$Sum$.

$2(a_1-a_2)$ 和 $2(b_1-b_2)$都是已知的项，分别设为 $a$ 和 $b$ .

所以它又变成了我们亲切的小学奥数之解方程：$ax+by=Sum$

对于二维的答案是 $(x,y)$ ，$x$ 和 $y$ 都可以通过高斯消元的模板来解出。

对于更高的维数，跟二维同理，只不过”元”多了几个而已。

所以就这样愉快的A掉了这道大水题。

Code:

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
using namespace std;
const int N=25;
const double eps=1e-8;
double v[N][N],f[N][N],s[N],del;
int n;
inline bool Gauss(){
	for(RI k=1,i=1;i<=n;++i,k=i){
		for(RI j=i+1;j<=n;++j)if(abs(f[j][i])>abs(f[k][i]))k=j;
		if(fabs(del=f[k][i])<eps)return false;//不判就出BUG，不知道为啥
		swap(f[i],f[k]);swap(s[i],s[k]);
		for(RI j=i;j<=n;++j)f[i][j]/=del;s[i]/=del;
		for(k=1;k<=n;++k)if(k!=i){
			del=f[k][i];
			for(RI j=i;j<=n;++j)f[k][j]-=f[i][j]*del;
			s[k]-=s[i]*del;
		}
	}return true;
}
int main(){
    scanf("%d",&n);
    for(RI i=1;i<=n+1;++i)for(RI j=1;j<=n;++j)scanf("%lf",&v[i][j]);
    for(RI i=1;i<=n;++i)
       for(RI j=1;j<=n;++j){
           s[i]+=(v[i][j]*v[i][j]-v[i+1][j]*v[i+1][j]);//求上面的 "Sum"
		   f[i][j]=2*(v[i][j]-v[i+1][j]);//求上面的 "a"、"b"等
	   }
	Gauss();
	for(RI i=1;i<n;++i)printf("%.3lf ",s[i]);//注意输出格式!
	printf("%.3lf",s[n]);
	return 0;
}

这题啥都好，就是输出格式有点制杖……请各位小心……

本文标题:【题解】 [JSOI2008]球形空间产生器高斯消元洛谷P4035

文章作者:Qiuly

发布时间:2019年02月14日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/14/[题解]luoguP4035/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。